package org.ala.everyday;

/**
 * 给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
 *
 * 你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aabaaaacaabc", k = 2
 * 输出：8
 * 解释：
 * 从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
 * 从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
 * 共需要 3 + 5 = 8 分钟。
 * 可以证明需要的最少分钟数是 8 。
 * 示例 2：
 *
 * 输入：s = "a", k = 1
 * 输出：-1
 * 解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 105
 * s 仅由字母 'a'、'b'、'c' 组成
 * 0 <= k <= s.length
 *
 * @author ala
 * @date 2024-09-27 01:06
 */
public class Q2516 {

    public static void main(String[] args) {
        Q2516 q = new Q2516();

//        String s = "aabaaaacaabc";
//        int k = 2;

        String s = "caaa";
        int k = 1;

//        String s = "caaababcaa";
//        int k = 2;

        System.out.println(q.takeCharacters(s, k));
    }

    public int takeCharacters(String s, int k) {
        return V1(s, k);
    }
    /**
     *  1）假设 s 中有a个a，b个b，c个c，那把需要的abc挖出来后，剩余的子串至多有 a-k, b-k, c-k 个abc
     *      所以问题变成：从 s 中找一个最长子串，其至多有 a-k, b-k, c-k 个 abc
     *                  从 s 中找一个最长子串，其外部至少有 k,k,k 个abc
     *  2）滑窗，维护窗口外部 abc 的数量
     *      若某个字母数量降到k以下，说明滑窗太大了，要吐出来一点
     *      若所有字母都超过k，说明滑窗太小了，要继续吃
     *      过程中记录下滑窗的最大长度
     */
    protected int V1(String s, int k) {
        char[] cs = s.toCharArray();
        int N = cs.length;
        if (N < 3 * k) {return -1;}

        //  每种字母的数量
        int[] cnts = new int[] {0,0,0};
        for (char c: cs) {
            cnts[c - 'a']++;
        }
        if (cnts[0] < k || cnts[1] < k || cnts[2] < k) {
            return -1;
        }
        //  滑窗
        int l = 0, r = -1, res = 0;
        while (r < N-1) {
            int c = cs[++r] - 'a';
            cnts[c]--;
            while (l <= r && cnts[c] < k) {
                cnts[cs[l++] - 'a']++;
            }
            res = Math.max(res, r - l + 1);
        }

        return N - res;
    }


}
